import java.util.Stack;
import java.util.*;
import java.util.ArrayList;
class Solution {
    public boolean backspaceCompare(String s, String t){
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();
        for (int i = 0; i < ch1.length; i++){
            if (ch1[i] == '#'){
                if (!stack1.empty()){
                    stack1.pop();
                }

            }else{
                stack1.push(ch1[i]);
            }
        }
        for (int j = 0; j < ch2.length; j++){
            if (ch2[j] == '#'){
                if (!stack2.empty()){
                    stack2.pop();
                }

            }else{
                stack2.push(ch2[j]);
            }
        }
        while (!stack1.empty() && !stack2.empty()){
            if (stack1.peek() != stack2.peek()){
                return false;
            }
            stack1.pop();
            stack2.pop();
        }
        return stack1.empty() && stack2.empty();
    }
}
class Solution4 {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < ops.length; i++){
            String val = ops[i];
            if (!isOperation(val)){
                stack.push(Integer.parseInt(val));
            }else{

                switch(val){
                    case "+" :
                        int num2 = stack.pop();
                        int num1 = stack.peek();
                        stack.push(num2);
                        stack.push(num2 + num1);
                        break;
                    case "C" :
                        stack.pop();
                        break;
                    case "D" :
                        stack.push(2 * stack.peek());
                        break;
                }
            }
        }
        int sum = 0;
        while (!stack.empty()){

            sum += stack.peek();
            stack.pop();
        }
        return sum;
    }
    public boolean isOperation(String x){
        if (x.equals("+") || x.equals("C") || x.equals("D")){
            return true;
        }
        return false;
    }
}



class Solution5 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }

        }
        return stack.empty();
    }
}

class StockSpanner{
    Stack<Integer> pricestack;
    Stack<Integer> widthstack;
    public StockSpanner(){
        this.pricestack = new Stack<>();
        this.widthstack = new Stack<>();

    }
    public int next(int price){
        int width = 1;
        while (!pricestack.empty() && pricestack.peek() <= price){
            pricestack.pop();
            width += widthstack.pop();
        }
        pricestack.push(price);
        widthstack.push(width);
        return width;

    }
}
class Solution2{
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++){
            String val = tokens[i];
            if (!isOperation(val)){
                stack.push(Integer.parseInt(val));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (val){
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                    case "*" :
                        stack.push(num1 * num2);
                        break;
                    case "/" :
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();

    }
    public boolean isOperation(String x){
        if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")){
            return  true;
        }else {
            return  false;
        }
    }

}
public class ListZuoye {
}
